package com.algorithm;

/**
 * @Author: Gallrax
 * @Description:
 * @Date: 2019/1/3
 */
public class TenAlgorithms {

    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] array) {
        boolean isChange;
        //外层循环表示当前为第几次循环
        for (int i = 0; i < array.length - 1; i++) {
            //如果没有改变则说明该数组顺序已经是正确的顺序
            isChange = false;
            //内层循环则是进行比较，当前圈数选出最大值
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isChange = true;
                }
            }
            //优化
            if (!isChange) return;
        }
    }

    /**
     * 选择排序
     */
    public static void selectSort(int[] array) {
        //最小下标临时变量
        int minIndex;
        //外层循环(-1的原因是最后比较的最后一个元素在内循环中)
        for (int i = 0; i < array.length - 1; i++) {
            //将最小下标初始化为当前外层循环的小标
            minIndex = i;
            //从外层循环的下标后开始循环至最后一个，寻找比当前下标对应值更小的值对应的下标，并替换minIndex
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }

    /**
     * 插入排序
     */
    public static void insertSort(int[] array) {
        //外层循环(之所以初始化i=1是因为如果i=则第一次比比较完全没有意义，因为从下标为1开始，至少还会比较下标为0的元素)
        for (int i = 1; i < array.length; i++) {
            //内层循环比较当前下标为i之前的所有元素
            //第一种方式
            for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
                swap(array, j, j - 1);
            }
            //第二种方式(第一种方式的详细版)
            /*for (int j = i; j > 0; j--) {
                if (array[j] < array[j - 1]) {
                    swap(array, j, j - 1);
                } else {
                    break;
                }
            }*/

        }
    }

    /**
     * 希尔排序
     */
    public static void shellSort(int[] array) {
        //增量
        int gap = array.length / 2;
        while (gap > 0) {
            for (int i = 0; i < array.length; i++) {
                //进行插入排序
                for (int j = i; j < array.length - gap; j += gap) {
                    if (array[j] > array[j + gap]) {
                        swap(array, j, j + gap);
                    }
                }
            }
            gap = gap / 2;
        }
    }

    /**
     * 归并排序
     */
    public static void mergeSort(int[] array) {
        int[] newArray = new int[array.length];
        mergeSort(array, newArray, 0, array.length - 1);
    }

    private static void mergeSort(int[] array, int[] newArray, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(array, newArray, left, mid);//排序左侧
            mergeSort(array, newArray, mid + 1, right);//排序右侧
            merge(array, newArray, left, mid, right);//合并两侧并排序
        }
    }

    private static void merge(int[] array, int[] newArray, int left, int mid, int right) {
        int tempLeftIndex = left;
        int tempRightIndex = mid + 1;
        int newArrayIndex = 0;
        while (tempLeftIndex <= mid && tempRightIndex <= right) {
            if (array[tempLeftIndex] <= array[tempRightIndex]) {
                newArray[newArrayIndex++] = array[tempLeftIndex++];
            } else {
                newArray[newArrayIndex++] = array[tempRightIndex++];
            }
        }
        //说明其中一侧已经全部填充至新的数组中
        //如果做左侧还有未填充的，则将左侧的按照顺序追加至新数组后面
        while (tempLeftIndex <= mid) {
            newArray[newArrayIndex++] = array[tempLeftIndex++];
        }
        //如果右侧还有未填充的，则将右侧的按照顺序追加至数组后面
        while (tempRightIndex <= right) {
            newArray[newArrayIndex++] = array[tempRightIndex++];
        }
        newArrayIndex = 0;
        //将newArray中的值依次填充至array从left下标开始到rigt下标(newArray.lenth = right - left)
        while (left <= right) {
            array[left++] = newArray[newArrayIndex++];
        }
    }

    /**
     * 快速排序
     */
    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    private static void quickSort(int[] array, int left, int right) {
        if (right - left <= 0) {
            return;
        } else {
            int partiton = partiton(array, left, right);
            quickSort(array, left, partiton - 1);//快速排序比基准小的一侧
            quickSort(array, partiton + 1, right);//快速排序比基准大的一侧
        }
    }

    private static int partiton(int[] array, int left, int right) {
        int pivot = array[right];//设置基准
        int tempLeftIndex = left - 1;//左移的指针
        int tempRightIndex = right;//由移的指针
        while (true) {
            //当不再循环则说明找到比基准大的值
            while (array[++tempLeftIndex] < pivot) {
            }
            //当不再循环则说明找到比基准小的值
            while (tempRightIndex > 0 && array[--tempRightIndex] > pivot) {
            }
            //如果左移的下标大于等于右移的下标则说明所有元素都已经比较完毕
            if (tempLeftIndex >= tempRightIndex) {
                break;
            } else {
                //交换
                swap(array, tempLeftIndex, tempRightIndex);
            }
        }
        //此步是将左侧最后一个比基准大的和右侧最后一个比基准小的交换
        swap(array, tempLeftIndex, right);
        return tempLeftIndex;
    }

    private static void swap(int[] array, int i, int j) {
        if (array == null || array.length < i || array.length < j) {
            throw new RuntimeException("数组格式错误");
        }
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void printArray(int[] array) {
        StringBuilder sb = new StringBuilder();
        for (int i : array) {
            sb.append(i + " ");
        }
        System.out.println(sb.toString());
    }
}
